#pragma once
#include <iostream>
#include <vector>
#include <cmath>
#include<limits>
#include<fstream>
#include<string>
#include <algorithm>
#include <memory>
#include <cwchar>
#include <locale>
#include <codecvt>

using namespace std;
// 定义飞行线的结构体
struct FlightLine {
    int id; // 飞行线ID
    double x1, y1, x2, y2; // 飞行线的两个端点坐标
};

// 定义查询点的结构体
struct QueryPoint {
    double x, y; // 查询点坐标
};

// KD树的节点
struct KDNode {
    double point[2]; // [x, y]
    int id; // 飞行线ID
    shared_ptr<KDNode> left;
    shared_ptr<KDNode> right;

    KDNode(double x, double y, int id) : id(id), left(nullptr), right(nullptr) {
        point[0] = x;
        point[1] = y;
    }
};

class Calculate {
private:
    int Flight_num, QueryPoint_num;//飞行线数量与查询点数量
    vector < vector < wstring >> FlightData, QueryPointData, QueryPointData_Point;
    vector<int> results;// = findNearestFlightLine(flightLines, queryPoints);
public:
    vector<FlightLine> FlightLines;
    vector<QueryPoint> QueryPoints;
    //int cs;

    Calculate();

    int Get_Flight_num();

    int Get_QueryPoint_num();

    wstring Point_wstringtext(int num);

    void Get_FlightDataReference(vector<vector<wstring>>& newdata);

    void Get_QueryPointDataReference(vector<vector<wstring>>& newdata);

    void Get_QueryPointData_PointReference(vector<vector<wstring>>& newdata);

    int Read_txtFile(wstring Wstring_file_path);

    // 构建KD树
    shared_ptr<KDNode> buildKDTree(vector<FlightLine>& flightLines, int depth = 0);

    // 计算两点距离的平方（避免开方提高效率）
    double distanceSquared(double x1, double y1, double x2, double y2);

    // KD树最近邻搜索
    void nearestNeighborSearch(shared_ptr<KDNode> node, const QueryPoint& query, int depth, double& minDist, int& nearestId);

    // 计算点到线段的最短距离（与之前相同）
    double pointToLineDistance(double px, double py, double x1, double y1, double x2, double y2);

    // 使用KD树优化查找最近飞行线
    vector<int> findNearestFlightLineKDTree(const vector<FlightLine>& flightLines, const vector<QueryPoint>& queryPoints);

    //暴力方法求解最近飞行线
    void findNearestFlightLine(const vector<FlightLine>& flightLines, const vector<QueryPoint>& queryPoints);
};
